package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/1/
 * <p>
 * 解题  https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode/
 */
public class 前序遍历 extends 二叉树Case {

	@Test
	public void test() {
//		1
//       \
//		  2
//		 /
//		3
		TreeNode node1 = new TreeNode(1);
		TreeNode node2 = node1.right = new TreeNode(2);
		TreeNode node3 = node2.left = new TreeNode(3);

		Assert.assertEquals(Arrays.asList(1, 2, 3), preorderTraversal(node1));
	}

	/**
	 * 前序遍历 递归
	 *
	 * @param root
	 *
	 * @return
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		help(root, res);
		return res;
	}

	private void help(TreeNode node, List<Integer> res) {
		if (node == null) {
			return;
		}
		res.add(node.val);

		if (node.left != null) {
			help(node.left, res);
		}
		if (node.right != null) {
			help(node.right, res);
		}
	}

//	/**
//	 * 前序遍历 栈的方法
//	 *
//	 * @param root
//	 */
//	public List<Integer> preorderTraversal(TreeNode root) {
//		Stack<TreeNode> stack  = new Stack<>();
//		List<Integer>   output = new ArrayList<>();
//
//		if (root == null) {
//			return output;
//		}
//
//		stack.push(root);
//
//		while (!stack.isEmpty()) {
//			TreeNode node = stack.pop();
//
//			// 先访问根节点
//			output.add(node.val);
//
//			if (node.right != null) {
//				stack.push(node.right);
//			}
//			if (node.left != null) {
//				stack.push(node.left);
//			}
//		}
//		return output;
//	}

}
